
#include<iostream>
#include<stdio.h>

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partSort(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		swap(a + left, a + right);
	}
	swap(a + left, a + keyi);
	return left;
}

void quickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	else
	{
		int keyi = partSort(a, begin, end);
		quickSort(a, begin,keyi - 1);
		quickSort(a, keyi + 1,end);
	}
}


void bubbleSort(int* a, int n, int i)
{
	bool exchange;
	if (i == n - 1)
	{
		return;
	}
	else
	{
		for (int j = n - 1; j > i; --j)
		{
			if (a[j] < a[j - 1])
			{
				swap(a + j, a + j - 1);
				exchange = true;
			}
		}
		if (exchange)
			bubbleSort(a, n, i + 1);
		else
			return;
	}
}

//int main()
//{
//	int arr[] = { 9,6,5,4,8,4,3,6,2,7 };
//	//bubbleSort(arr, 10, 0);
//	quickSort(arr, 0, 9);
//	for (auto e : arr)
//	{
//		std::cout << e << " ";
//	}
//	return 0;
//}